//21. 合并两个有序链表
//思路：创建一个头指针，一个尾指针，遍历两个数组，如果有一个数组被遍历完就结束
//在循环里面判断指针的 val 大小，将小进行尾插
//最后将没有遍历完的结构体指针加尾插，再返回头指针
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (NULL == list1)
        return list2;
    if (NULL == list2)
        return list1;

    struct ListNode* head = NULL, * tail = NULL;
    while (list1 && list2)//有一个为空就跳出，后面直接把不为空的接上就可以
    {
        //尾插
        if (list1->val < list2->val)
        {
            if (NULL == tail)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }

            list1 = list1->next;
        }
        else
        {
            if (NULL == tail)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }

            list2 = list2->next;
        }
    }

    if (NULL == list1)//list1为空，直接把list2接在后面
        tail->next = list2;
    else
        tail->next = list1;

    return head;
}